Degré d'un sommet, sommet isolé, sommets adjacents

Définitions Degré d’un sommet, sommet isolé, sommets adjacents

• Le degré d’un sommet est le nombre d’arêtes qui partent de ce sommet ou y arrivent (les boucles comptent donc deux fois). Dans le cas d’un graphe orienté, on parle de degré entrant et de degré sortant d’un sommet.
  
• Un sommet est dit isolé s’il est de degré  \(0\) (aucune arête n’en part ni y arrive).
  
• Deux sommets sont dits adjacents s’ils sont reliés par (au moins) une arête.
  

Propriété

Dans un graphe, la somme des degrés des sommets est égale au double du nombre d’arêtes.

Conséquence

Dans un graphe, il ne peut y avoir qu'un nombre pair de sommets de degré impair.

Exemple

Les sommets A et B sont adjacents car reliés par un segment qu'on appelle arête.
Les sommets A et D ne sont pas adjacents.
Le sommet E n'étant relié à aucun autre sommet est dit sommet isolé.
Le degré d'un sommet est le nombre d'arêtes reliées à ce sommet. Ici, le degré des sommets A et C est 2, le degré du sommet B est 3, le degré du sommet D est 1, le degré du sommet E est 0.
Il y a bien un nombre pair de sommets de degré impair (il y en a deux qui sont les sommets B et D).
La somme des degrés est  \(2+3+2+1+0=8\)  qui est bien le double du nombre d'arêtes.